package com.example.tencentTrain;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Leetcode78_Subsets {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        List<List<Integer>> res = new Solution().subsets(nums);
        res.forEach(r -> System.out.println(r));
    }

    static class Solution {
        /**
         * 回溯(递归实现)
         * @param nums
         * @return
         */
        public List<List<Integer>> subsets2(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Deque<Integer> stack = new LinkedList<>();
            backTrack(res, stack, nums, 0);

            return res;
        }

        private void backTrack(List<List<Integer>> res, Deque<Integer> stack, int[] nums, int cur) {
            if (cur == nums.length) {
                res.add(new ArrayList<>(stack));
                return;
            }

            stack.addLast(nums[cur]);
            backTrack(res, stack, nums, cur + 1); // 代表将前面的所有元素都选了
            stack.removeLast(); // 不选cur
            backTrack(res, stack, nums, cur + 1); // 到这里前面(0~cur)哪些选了，哪些没选就已经确定，但是后面的(cur+1 ~ n)还没定

        }

        /**
         * 迭代(结合位运算)
         * n个元素用n为表示 0表示子集中不包含该索引对应的元素, 1表示包含
         * 即总共有(2^n - 1)种组合的情况
         * @param nums
         * @return
         */
        public List<List<Integer>> subsets1(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Deque<Integer> stack = new LinkedList<>();
            int len = nums.length;
            int total = 1 << nums.length;
            for (int mask = 0; mask < total; mask++) { // 遍历每一种组合的情况
                stack.clear();
                for (int j = 0; j < len; j++) { // 将当前组合该有的元素加入到集合中
                    if ((mask & (1 << j)) != 0) {
                        stack.addLast(nums[j]);
                    }
                }

                res.add(new ArrayList<>(stack));
            }
            return res;
        }

        public List<List<Integer>> subsets(int[] nums) {
            return subsets2(nums);
        }
    }
}
